package com.cqs.leetcode.dp;

/**
 * lixw
 * 2023/3/30
 **/
public class BestTime123 {

    /**
     * 1. 每天会有五种状态。
     * 2. 同一天可以交易多次
     * 3. dp[i][j] 表示第i天的第j种状态的最大收益
     *
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][5];
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);
            dp[i][2] = Math.max(dp[i][1] + prices[i], dp[i - 1][2]);
            dp[i][3] = Math.max(dp[i][2] - prices[i], dp[i - 1][3]);
            dp[i][4] = Math.max(dp[i][3] + prices[i], dp[i - 1][4]);
        }
        return dp[prices.length - 1][4];
    }

    public static void main(String[] args) {
        BestTime123 b = new BestTime123();
        System.out.println(b.maxProfit(new int[]{3,3,5,0,0,3,1,4}));
        System.out.println(b.maxProfit(new int[]{7,6,4,3,1}));
        System.out.println(b.maxProfit(new int[]{1,2,3,4,5}));
    }


}
